{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Calculate Amount Paid in Taxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calculateTax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算应缴税款总额"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>brackets</code> ，其中 <code>brackets[i] = [upper<sub>i</sub>, percent<sub>i</sub>]</code> ，表示第 <code>i</code> 个税级的上限是 <code>upper<sub>i</sub></code> ，征收的税率为 <code>percent<sub>i</sub></code> 。税级按上限 <strong>从低到高排序</strong>（在满足 <code>0 &lt; i &lt; brackets.length</code> 的前提下，<code>upper<sub>i-1</sub> &lt; upper<sub>i</sub></code>）。</p>\n",
    "\n",
    "<p>税款计算方式如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>不超过 <code>upper<sub>0</sub></code> 的收入按税率 <code>percent<sub>0</sub></code> 缴纳</li>\n",
    "\t<li>接着 <code>upper<sub>1</sub> - upper<sub>0</sub></code> 的部分按税率 <code>percent<sub>1</sub></code> 缴纳</li>\n",
    "\t<li>然后 <code>upper<sub>2</sub> - upper<sub>1</sub></code> 的部分按税率 <code>percent<sub>2</sub></code> 缴纳</li>\n",
    "\t<li>以此类推</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>income</code> 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 <code>10<sup>-5</sup></code> 的结果将被视作正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>brackets = [[3,50],[7,10],[12,25]], income = 10\n",
    "<strong>输出：</strong>2.65000\n",
    "<strong>解释：</strong>\n",
    "前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。\n",
    "接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。\n",
    "最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。\n",
    "需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>brackets = [[1,0],[4,25],[5,50]], income = 2\n",
    "<strong>输出：</strong>0.25000\n",
    "<strong>解释：</strong>\n",
    "前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。\n",
    "剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。\n",
    "需要支付的税款总计 $0 + $0.25 = $0.25 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>brackets = [[2,50]], income = 0\n",
    "<strong>输出：</strong>0.00000\n",
    "<strong>解释：</strong>\n",
    "没有收入，无需纳税，需要支付的税款总计 $0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= brackets.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= upper<sub>i</sub> &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= percent<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= income &lt;= 1000</code></li>\n",
    "\t<li><code>upper<sub>i</sub></code> 按递增顺序排列</li>\n",
    "\t<li><code>upper<sub>i</sub></code> 中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li>最后一个税级的上限大于等于 <code>income</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [calculate-amount-paid-in-taxes](https://leetcode.cn/problems/calculate-amount-paid-in-taxes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [calculate-amount-paid-in-taxes](https://leetcode.cn/problems/calculate-amount-paid-in-taxes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,50],[7,10],[12,25]]\\n10', '[[1,0],[4,25],[5,50]]\\n2', '[[2,50]]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res=pre=0\n",
    "        for m,r in brackets:\n",
    "            if  income <=m:\n",
    "                res += (income-pre)*r\n",
    "                break\n",
    "            res += (m-pre)*r\n",
    "            pre = m\n",
    "        return res/100 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for up,per in brackets:\n",
    "            ans += (min(up, income) - pre) * per * 0.01\n",
    "            if income <= up:\n",
    "                break\n",
    "            pre = up\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        brackets.insert(0,[0,0])\n",
    "        for i in range(1,len(brackets)):\n",
    "            if brackets[i][0] <= income:\n",
    "                tax += (brackets[i][0] - brackets[i-1][0]) * brackets[i][1] / 100\n",
    "            else:\n",
    "                tax += (income - brackets[i-1][0]) * brackets[i][1] / 100\n",
    "                break\n",
    "        return tax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        a=b=i=0\n",
    "        while brackets[i][0]<income:\n",
    "            a+=brackets[i][1]*(brackets[i][0]-b)/100\n",
    "            b=brackets[i][0]\n",
    "            i+=1\n",
    "        a+=brackets[i][1]*(income-b)/100\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        for i,j in brackets:\n",
    "            if income > i:\n",
    "                ans += (i - p) * j/100\n",
    "                p = i\n",
    "            else:\n",
    "                ans += (income - p) *j/100\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        b_index = 0\n",
    "        ans = 0\n",
    "        while b_index < len(brackets) and income > 0:\n",
    "            u, p = brackets[b_index]\n",
    "            if b_index == 0:\n",
    "                ans += min(u, income) * (p / 100)\n",
    "                income = income - u\n",
    "            else:\n",
    "                ans += min(u - brackets[b_index - 1][0], income) * (p / 100)\n",
    "                income = income - (u - brackets[b_index - 1][0])\n",
    "            b_index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        re = 0\n",
    "        pre = 0\n",
    "        for upper, per in brackets:\n",
    "            if income < upper:\n",
    "                re += (income-pre) * per * 0.01\n",
    "                break\n",
    "            re += (upper-pre) * per * 0.01\n",
    "            pre = upper\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax_sum = 0\n",
    "        n = len(brackets)\n",
    "        if income >= brackets[0][0]:\n",
    "            for i in range(1,n):\n",
    "                if income >= brackets[i][0]:\n",
    "                    tax_sum += (brackets[i][0]-brackets[i-1][0]) * brackets[i][1]/100\n",
    "                else:\n",
    "                    tax_sum += (income-brackets[i-1][0]) * brackets[i][1]/100\n",
    "                    break\n",
    "            tax_sum += brackets[0][0]*brackets[0][1]/100\n",
    "        else:\n",
    "            tax_sum = income*brackets[0][1]/100\n",
    "        return tax_sum\n",
    "\n",
    "# calculateTax([[3,50],[7,10],[12,25]],10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        for i, ran in enumerate(brackets):\n",
    "            if income > ran[0]:\n",
    "                if i == 0:\n",
    "                    ans += ran[0] * ran[1] / 100\n",
    "                else:\n",
    "                    ans += (ran[0] - brackets[i-1][0]) * ran[1] / 100\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += income * ran[1] / 100\n",
    "                else:\n",
    "                    ans += (income - brackets[i-1][0]) * ran[1] / 100\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        n = len(brackets)\n",
    "        ans += min(income, brackets[0][0])*brackets[0][1]\n",
    "        for i in range(1, n):\n",
    "            cur = min(income, brackets[i][0]) - brackets[i-1][0]\n",
    "            if cur > 0:\n",
    "                ans += cur*brackets[i][1]\n",
    "        return ans/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans, used = 0, 0\n",
    "        for row in brackets:\n",
    "            line = row[0]\n",
    "            # print(\"row={}, used={}\".format(row, used))\n",
    "            if income > line:\n",
    "                ans += ((line-used) * row[1]/100)\n",
    "                used += (line-used)\n",
    "            else:\n",
    "                ans += (income-used) * row[1]/100\n",
    "                break\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "\n",
    "            prev = upper\n",
    "\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for u, p in brackets:\n",
    "            if income >= pre:\n",
    "                ans += (min(u, income) - pre) * (p / 100)\n",
    "                pre = u\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income < brackets[0][0]: return income * brackets[0][1] / 100\n",
    "        ans = brackets[0][0] * brackets[0][1] / 100\n",
    "        for i, bracket in enumerate(brackets):\n",
    "            if i == 0: continue\n",
    "            tax = bracket[0] - brackets[i-1][0] if income >= bracket[0] else income - brackets[i-1][0]\n",
    "            ans += tax * bracket[1] / 100 if tax > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if brackets[0][0] >= income:\n",
    "            ans = income * brackets[0][1] / 100\n",
    "            income = 0\n",
    "        else:\n",
    "            ans = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans,save = 0,0\n",
    "        for b in brackets:\n",
    "            if income <= 0:\n",
    "                return ans\n",
    "            ans += min(b[0]-save,income) * b[1] / 100\n",
    "            income -= b[0]-save\n",
    "            save = b[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, a: List[List[int]], x: int) -> float:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for u, p in a:\n",
    "            if pre>x:\n",
    "                break\n",
    "            res += (min(u, x)-pre)*p/100\n",
    "            pre = u\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        lowest=brackets[0][0]\n",
    "        lowest_rate=brackets[0][1]\n",
    "        if lowest>=income:\n",
    "            return income*lowest_rate/100\n",
    "        res=lowest*lowest_rate/100\n",
    "        \n",
    "        for i in range(1, len(brackets)):\n",
    "            if income<=brackets[i][0]:\n",
    "                res+=((income-lowest)*brackets[i][1]/100)\n",
    "                break\n",
    "            else:\n",
    "                res+=((brackets[i][0]-lowest)*brackets[i][1]/100)\n",
    "                lowest=brackets[i][0]\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        temp = income\n",
    "        prev = 0\n",
    "        for i in brackets:\n",
    "            if temp == 0:\n",
    "                break\n",
    "            elif income >= i[0]:\n",
    "                ans += (i[0] - prev) * (i[1] * 0.01)\n",
    "                prev = i[0]\n",
    "            else:\n",
    "                ans += (income - prev )* (i[1] * 0.01)\n",
    "                break \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax=lower=0\n",
    "        for upper,percent in brackets:\n",
    "            tax=(min(income,upper)-lower)*percent\n",
    "            totalTax+=tax\n",
    "            if income<=upper:\n",
    "                break\n",
    "            lower=upper\n",
    "        return totalTax/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return income\n",
    "        \n",
    "        if brackets[0][0]>=income:\n",
    "            money = income*brackets[0][1]/100\n",
    "            return money\n",
    "        else:\n",
    "            minus = income\n",
    "            org_income = income\n",
    "            money = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "            for i in range(1, len(brackets)):\n",
    "                if brackets[i][0] <= minus:\n",
    "                    # minus -= brackets[i - 1][0]\n",
    "                    income = brackets[i][0]-brackets[i - 1][0]\n",
    "                    money += (income * brackets[i][1] / 100)\n",
    "                    # print(brackets[i][0], brackets[i][1], income, money)\n",
    "                else:\n",
    "                    org_income -= brackets[i - 1][0]\n",
    "                    money += (org_income * brackets[i][1] / 100)\n",
    "                    return money\n",
    "            return money"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = pre = 0 \n",
    "        for up,rate in  brackets:\n",
    "            if  income <= up:\n",
    "                ans +=(income - pre)*rate\n",
    "                break\n",
    "            ans += (up-pre)*rate\n",
    "            pre = up\n",
    "        return  ans/100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper,percent in brackets:\n",
    "            tax = (min(income,upper)-lower)*percent\n",
    "            totalTax += tax\n",
    "            if income<=upper:break\n",
    "            lower = upper\n",
    "        return totalTax/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = income\n",
    "        ans = 0\n",
    "        last_upper = 0\n",
    "        for upper, percent in brackets:\n",
    "            if res >= upper:\n",
    "                ans += (upper-last_upper) * percent / 100\n",
    "            else:\n",
    "                ans += (res - last_upper) * percent / 100\n",
    "                return ans\n",
    "            last_upper = upper\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ret = 0\n",
    "        n = len(brackets)\n",
    "        start = 0\n",
    "        for i in range(n):\n",
    "            a, b = brackets[i]\n",
    "            if income <= a:\n",
    "                ret += (income - start) * b / 100\n",
    "                return ret\n",
    "            else:\n",
    "                ret += (a - start) * b / 100\n",
    "                start = a\n",
    "        # return ret + (income - d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income==0:\n",
    "            return 0\n",
    "        else:\n",
    "            s=0\n",
    "            for i in range(len(brackets)):\n",
    "                if i==0:\n",
    "                    if brackets[i][0]>=income:\n",
    "                        s+=income*brackets[i][1]/100\n",
    "                        income-=income\n",
    "                    else:\n",
    "                        s+=brackets[i][0]*brackets[i][1]/100\n",
    "                        income -= brackets[i][0]\n",
    "                else:\n",
    "                    if brackets[i][0]-brackets[i-1][0] < income:\n",
    "                        s+=(brackets[i][0]-brackets[i-1][0])*brackets[i][1]/100\n",
    "                        income-=brackets[i][0]-brackets[i-1][0]\n",
    "                    else:\n",
    "                        s+=income*brackets[i][1]/100\n",
    "                        income-=income\n",
    "            return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        n = len(brackets)\n",
    "        pre = 0\n",
    "        for up,per in brackets:\n",
    "            if income >= up:\n",
    "                ans += (up - pre) * per * 0.01\n",
    "                pre = up\n",
    "            else:\n",
    "                ans += (income - pre) * per * 0.01\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        target = 0\n",
    "        for i in range (len(brackets)):\n",
    "            if brackets[i][0] < income:\n",
    "                count += (brackets[i][0] - target) * 0.01 * brackets[i][1]\n",
    "                target = brackets[i][0]\n",
    "            else:\n",
    "                count += (income - target) * 0.01 * brackets[i][1]\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        pre = ans = 0\n",
    "        for x, y in brackets:\n",
    "            ans += max(0, min(income, x) - pre)  *  y\n",
    "            pre = x\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = start = 0\n",
    "        for upper, rate in brackets:\n",
    "            if income > upper:\n",
    "                tax += (upper - start) * rate \n",
    "                start = upper\n",
    "            elif income <= upper:\n",
    "                tax += (income - start) * rate\n",
    "                break\n",
    "            # print(upper, rate, tax, start)\n",
    "        return tax / 100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        n = len(brackets) \n",
    "        ans = 0 \n",
    "        pre = 0 \n",
    "        for i in range(n):\n",
    "            if income >= brackets[i][0]:\n",
    "                ans += (brackets[i][0]-pre) * brackets[i][1] \n",
    "                pre = brackets[i][0]\n",
    "            else:\n",
    "                ans += (income - pre) * brackets[i][1] \n",
    "                break \n",
    "        return ans / 100 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        brackets = [[0, 0]] + brackets\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        amount=0\n",
    "        lastUpper=0\n",
    "        for value in brackets:\n",
    "            amount+=(min(value[0],income)-lastUpper)*value[1]/100\n",
    "            # 更新税率上限\n",
    "            lastUpper=value[0]\n",
    "            if value[0]>=income:\n",
    "                break\n",
    "        return amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        for i, ran in enumerate(brackets):\n",
    "            if income > ran[0]:\n",
    "                if i == 0:\n",
    "                    ans += ran[0] * ran[1]\n",
    "                else:\n",
    "                    ans += (ran[0] - brackets[i-1][0]) * ran[1]\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += income * ran[1]\n",
    "                else:\n",
    "                    ans += (income - brackets[i-1][0]) * ran[1]\n",
    "                break\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        brackets = [[0, 0]] + brackets\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "\n",
    "        ans = prev = 0\n",
    "\n",
    "        for upper, percent in brackets:\n",
    "\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "\n",
    "            prev = upper\n",
    "\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for idx,(u,p) in enumerate(brackets):\n",
    "            if u <= income:\n",
    "                res += (u-pre)*(p/100)\n",
    "                pre = u\n",
    "            else:\n",
    "                res += (income-pre)*(p/100)\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        low = 0\n",
    "        for i in brackets:\n",
    "            if i[0] < income:\n",
    "                tax += (i[0] - low)*i[1]\n",
    "                low = i[0]\n",
    "            else:\n",
    "                tax += (income - low)*i[1]\n",
    "                break\n",
    "        return tax*0.01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans=0\n",
    "        i=0\n",
    "        for i in range(len(brackets)):\n",
    "            if brackets[i][0]>=income:\n",
    "                if i==0:\n",
    "                    return income*brackets[0][1]/100\n",
    "                for j in range(i):\n",
    "                    if j==0:\n",
    "                        ans+=brackets[0][0]*brackets[0][1]/100\n",
    "                    else:\n",
    "                        ans+=(brackets[j][0]-brackets[j-1][0])*brackets[j][1]/100\n",
    "                ans+=(income-brackets[i-1][0])*brackets[i][1]/100\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        alltax = lower = 0\n",
    "        for upper , percent in brackets:\n",
    "            tax=(min(income,upper)-lower)*percent\n",
    "            alltax += tax\n",
    "            if income <= upper :\n",
    "                break;\n",
    "            lower = upper\n",
    "        return alltax/100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        n = len(brackets)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if income < brackets[i][0]:\n",
    "                if i - 1 >= 0:\n",
    "                    diff = income - brackets[i - 1][0]\n",
    "                    ans += diff * brackets[i][1] / 100\n",
    "                else:\n",
    "                    ans += income * brackets[i][1] / 100\n",
    "                break\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += brackets[i][0] * brackets[i][1] / 100\n",
    "                    #print(brackets[i][0] * brackets[i][1] / 100)\n",
    "                else:\n",
    "                    diff = (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                    \n",
    "                    ans += diff\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for u, r in brackets:\n",
    "            if income <= last:\n",
    "                break\n",
    "            ans += (min(income, u) - last) * r / 100\n",
    "            last = u\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return income\n",
    "        \n",
    "        if brackets[0][0]>=income:\n",
    "            money = income*brackets[0][1]/100\n",
    "            return money\n",
    "        else:\n",
    "            minus = income\n",
    "            org_income = income\n",
    "            money = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "            for i in range(1, len(brackets)):\n",
    "                if brackets[i][0] <= minus:\n",
    "                    # minus -= brackets[i - 1][0]\n",
    "                    income = brackets[i][0]-brackets[i - 1][0]\n",
    "                    money += (income * brackets[i][1] / 100)\n",
    "                    # print(brackets[i][0], brackets[i][1], income, money)\n",
    "                else:\n",
    "                    org_income -= brackets[i - 1][0]\n",
    "                    money += (org_income * brackets[i][1] / 100)\n",
    "                    return money\n",
    "            return money"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, b: List[List[int]], income: int) -> float:\n",
    "        if b[0][0] >= income:\n",
    "            return income * b[0][1] / 100\n",
    "        ans = b[0][0] * b[0][1]\n",
    "        for i in range(1, len(b)):\n",
    "            if b[i][0] >= income:\n",
    "                ans += (income - b[i - 1][0]) * b[i][1]\n",
    "                break\n",
    "            ans += (b[i][0] - b[i - 1][0]) * b[i][1]\n",
    "            print(b[i][0], b[i - 1][0], b[i][1])\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - p) * percent\n",
    "            p = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        low = 0\n",
    "        for i in brackets:\n",
    "            if i[0] < income:\n",
    "                tax += (i[0] - low)*i[1]*0.01\n",
    "                low = i[0]\n",
    "            else:\n",
    "                tax += (income - low)*i[1]*0.01\n",
    "                break\n",
    "        return tax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for tax in brackets:\n",
    "            \n",
    "            upper = tax[0]\n",
    "            upper -= cur\n",
    "        \n",
    "            if upper > income:\n",
    "                res += income * tax[1] * 0.01\n",
    "                break\n",
    "            else:\n",
    "                res += upper * tax[1] * 0.01\n",
    "                \n",
    "                cur = tax[0]\n",
    "                income -= upper\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        for bracket in brackets:\n",
    "            if income > bracket[0] - tmp:\n",
    "                res += (bracket[0] - tmp)*(bracket[1]/100.0)\n",
    "                income = income - (bracket[0] - tmp)\n",
    "                tmp = bracket[0]\n",
    "            elif income > 0:\n",
    "                res += income * (bracket[1] / 100.0)\n",
    "                income = 0\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if len(brackets) == 0:\n",
    "            return 0\n",
    "        \n",
    "        result = 0.0\n",
    "        pre = 0\n",
    "        for bracket in brackets:\n",
    "            if income > bracket[0]:\n",
    "                result = result + (bracket[0] - pre) * bracket[1]\n",
    "                pre = bracket[0]\n",
    "            else:\n",
    "                result = result + (income - pre) * bracket[1]\n",
    "                break\n",
    "        return result / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        if income == 0:\n",
    "            return 0\n",
    "        for i in range(len(brackets)):\n",
    "            if len(brackets) == 1:\n",
    "                if income - brackets[0][0] == 0:\n",
    "                    tax = brackets[0][0] * (brackets[0][1] / 100)\n",
    "                else:\n",
    "                    # tax = abs(income - brackets[0][0]) * (brackets[0][1] / 100)\n",
    "                    tax = income * (brackets[0][1] / 100)\n",
    "                break\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    if income < brackets[i][0]:\n",
    "                        # return round(abs(income-brackets[0][0])* (brackets[0][1] / 100),2)\n",
    "                        return round(income* (brackets[0][1] / 100),2)\n",
    "                    else:\n",
    "                        tax = brackets[0][0] * (brackets[0][1] / 100)\n",
    "                elif income > brackets[i][0]:\n",
    "                    tax += (brackets[i][0] - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                elif income == brackets[i][0]:\n",
    "                    tax += (income - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                    break\n",
    "                elif income < brackets[i][0]:\n",
    "                    tax += (income - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                    break\n",
    "\n",
    "        return round(tax, 2)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
